Problems tagged with "minimum spanning trees"

Answer: 8. Every spanning tree of a graph with \(|V|\) nodes is a tree on those \(|V|\) nodes, so it has exactly \(|V| - 1 = 8\) edges.

True. Node \(b\) has only two edges: \((a, b)\) with weight 5 and \((b, d)\) with weight 7. A spanning tree must include at least one of them. If a spanning tree used \((b, d)\) but not \((a, b)\), adding \((a, b)\) would create a cycle containing \((b, d)\); removing \((b, d)\) gives another spanning tree with smaller total weight. So every minimum spanning tree contains \((a, b)\).

False. Consider a triangle on nodes \(u\), \(v\), and \(w\) with edge weights \(w(u, v) = 3\), \(w(u, w) = 2\), and \(w(w, v) = 2\). The unique MST uses edges \((u, w)\) and \((w, v)\), so the path from \(u\) to \(v\) in the MST has length 4. But the unique shortest path from \(u\) to \(v\) is the single edge \((u, v)\), with length 3.

(a, d), (a, c), (a, b), (c, e). Kruskal's algorithm considers edges in increasing order of weight: (a, d) with weight 2, (a, c) with weight 5, (a, b) with weight 7, and (c, e) with weight 9 are each added since none creates a cycle. The remaining edges, (b, d) with weight 20 and (a, e) with weight 21, would create cycles.

False. When there are ties in the edge weights, the MST each algorithm returns depends on how the ties are broken, and the two algorithms consider edges in different orders. For example, in a triangle whose three edges all have the same weight, each algorithm could return any of the three MSTs, depending on the order in which it considers the edges.

True. Processing edges in descending order of weight is the same as running ordinary Kruskal's algorithm on the graph with every weight negated. That finds a minimum spanning tree of the negated graph, which is a maximum spanning tree of the original graph.